Millions of checkers players worldwide can put down their pieces -- the ancient game has been solved, according to researchers.
Chinook, a computer program developed by researchers at the University of Alberta, can now play a perfect game of checkers. Chinook can recognize every possible move made in a checkers game and determine the correct counter move. If neither player makes a mistake, the game will end in a draw.
"The checkers result pushes the boundary of artificial intelligence," Dr. Jonathan Schaeffer, the head of the university's computer science department, wrote in the paper that will be released Friday in the journal Science.
Since 1989, an average of 50 computers at a time worked around the clock to decipher the game's 500 billion billion possible moves.
Schaeffer developed the Chinook program with the initial goal of winning the Checkers World Championship against some of the best human players in the world.
In 1992, the computer was narrowly defeated by world champion Marion Tinsley, who is widely regarded as the best human checkers player ever. In 1994 it won the championship in a rematch against Tinsley. Chinook was then retooled to make it better and stronger, and to solve the game of checkers. According to Schaeffer, that goal was achieved.
"In 1994, it was extremely strong, but not perfect," he said. "The new program is perfect in the sense that it knows that if it doesn't make mistake and you don't make a mistake [the match] will always end in a draw."
Industrious players can study Schaeffer's proof to become stronger players, he said."You can now see how to not lose every single play," he said.
Despite Chinook's advance, Schaeffer, who was once a competitive chess player, doesn't believe that the solution will affect tournament play.
"Why do you play a competitive game like checkers? The intellectual challenge, the beauty of the creations that you make, the social aspects of the game," he said.
Richard Beckwith, the players' representative for the American Checkers Federation and a scientist at Ricerca Biosciences in Concord, Ohio, agreed.
"I applaud Mr. Schaeffer's artificial intelligence achievement, as he has been hard at work for many years on this project. However, the fact that the game is a draw (if both players play optimally) was known long ago as a result of much human analysis," he said in an e-mailed statement. "I don't expect any impact on face-to-face competition, as no human can possibly memorize the billions of combinations that Mr. Schaeffer has covered. Checkers still remains a highly strategic game when played head-to-head."
At high level competitions draws are already common, as top level players are often very knowledgeable about the game's strategy.
For Schaeffer, Chinook is just the beginning. The first man-machine poker match is set to take place in Las Vegas next week, and another University of Alberta computer will compete.
"The checkers is ending… and the poker is ongoing," he said. "Finally we have programs that are competitive with players. This will be a good test. … I hope it's not a painful lesson."
7/18/2007 Chinook Solves Checkers? by Dr. Richard Beckwith